﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 图解算法数据结构._24_ReverseList
{
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int x) { val = x; }
    }

    class MainProject
    {
        static void Main(string[] args)
        {

            ListNode root = new ListNode(1);
            root.next = new ListNode(2);
            root.next.next = new ListNode(3);
            root.next.next.next = new ListNode(4);
            root.next.next.next.next = new ListNode(5);
            Console.WriteLine(ReverseList(root));
            Console.WriteLine("执行到这了");
            Console.ReadKey();
        }
        public static ListNode ReverseList(ListNode head)
        {
            #region 辅助栈
            //if (head == null) return null;

            //Stack<int> stack = new Stack<int>();
            //while (head != null)
            //{
            //    stack.Push(head.val);
            //    head = head.next;
            //}

            //ListNode root = new ListNode(stack.Pop());

            //ListNode middle = root;
            //while (stack.Count>0)
            //{
            //    middle.next = new ListNode(stack.Pop());
            //    middle = middle.next;
            //}
            //return root;
            #endregion

            #region 递归遍历
            if (head == null)
            {
                return null;
            }

            ListNode root = null; 

            Recursion(head, head.next,ref root);
            head.next = null;
            return root;
            #endregion
        }

        public static void Recursion(ListNode preNode,ListNode curNode ,ref ListNode root)
        {
            if (curNode == null)
            {
                root = preNode;
                return;
            }

            Recursion(curNode, curNode.next, ref root);

            curNode.next = preNode;
        }
    }
}
